import java.util.*;

public class test {
    // leetcode 942.增减字符串匹配
    public int[] diStringMatch(String s) {
        int n = s.length();
        int left = 0;
        int right = n;
        int index = 0;
        int[] arr = new int[n + 1];
        for(int i = 0;i < n;i++){
            char c = s.charAt(i);
            if(c == 'I'){
                arr[index++] = left++;
            }else {
                arr[index++] = right--;
            }
        }
        arr[index] = left;
        return arr;
    }
    // leetcode 553.最优除法
    public String optimalDivision(int[] nums) {
        StringBuilder sb = new StringBuilder();
        int n = nums.length;
        for(int i = 0;i < n;i++) {
            sb.append(nums[i]);
            if (i != n - 1) sb.append('/');
            if (n > 2) {
                if (i == 0) sb.append('(');
                if (i == n - 1) sb.append(')');
            }
        }
        return sb.toString();
    }
    // leetcode 45.跳跃游戏Ⅱ
    // 1. 动态规划 -> O(n^2)
    public int jump1(int[] nums) {
        int n = nums.length;
        // 1. 创建dp表
        int[] dp = new int[n];
        // 2. 初始化
        Arrays.fill(dp,0x3f3f3f3f);//表示没有被跳到过
        dp[0] = 0;
        // 3. 填表
        for(int i = 0;i < n - 1;i++){
            int num = nums[i];
            for(int j = i + 1;j <= i + num && j < n;j++){
                dp[j] = Math.min(dp[i] + 1,dp[j]);
            }
        }
        // 4. 返回值
        return dp[n - 1];
    }
    // 2. 贪心 -> O(Nlogn)
    public int jump2(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        // 存储"每一层"跳跃结点
        // 贪心1:优先遍历(能够到达最远位置)的结点
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> (b[0] + b[1]) - (a[0] + a[1]));
        queue.add(new int[]{0,nums[0]});
        int num = 0;
        while(true){
            num++;
            int[] temp = queue.poll();
            int index = temp[0];
            int max = temp[1];
            if(index + max >= n - 1){
                return num;
            }
            // 贪心2:如果(遇到的新结点)所能到达的最远位置不如(当前)最远位置,
            // 则无意义,不进行存储
            for(int i = index + 1;i <= index + max && i < n;i++){
                if (queue.size() > 0) {
                    int[] t = queue.peek();
                    if (i + nums[i] > t[0] + t[1]) {
                        queue.add(new int[]{i, nums[i]});
                    }
                }else {
                    queue.add(new int[]{i, nums[i]});
                }
            }
        }
    }
    // 3. 贪心优化 -> O(n)
    public int jump(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        // 记录"当前能跳到的最大值"和"下一次能跳到的最大值"
        int jumpnum = 0;
        int nowjump = 0;
        int nextjump = 0;
        for(int i = 0;i < n - 1;i++){
            nextjump = Math.max(i + nums[i],nextjump);
            if(i >= nowjump){
                jumpnum++;
                nowjump = nextjump;
            }
        }
        return jumpnum;
    }
}
